package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         291,
		Discription: "字符串模板匹配（字符规律）不带空格的",
		Level:       2,
		Labels: map[string]int{
			"哈希表":  1,
			"双射": 1,
			"递归": 1,
			"回溯": 1,
		},
	})
}

func WordPatternMatch(pattern string, s string) bool {
	fx := make(map[byte]string, 0)
	rx := make(map[string]byte, 0)
	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		if i == len(pattern) && j == len(s) {
			return true
		}

		if i >= len(pattern) || j >= len(s) {
			return false
		}

		ch := pattern[i]
		fxWord, exist1 := fx[ch]
		//遍历从s的开始位置到结尾的不同长度的字符串
		for end := j + 1; end <= len(s); end++ {
			word := s[j:end]
			rxCh, exist2 := rx[word]

			if !exist1 && !exist2 {
				fx[ch] = word
				rx[word] = ch
				if dfs(i+1, end) {
					return true
				}
                
				//无法匹配回溯状态
				delete(fx, ch)
				delete(rx, word)
				continue
			}

			if exist1 && exist2 && fxWord == word && rxCh == ch && dfs(i+1, end) {
				return true
			}
		}

		return false
	}

	return dfs(0, 0)
}